#include<iostream>
#include<vector>
using namespace std;

//class Solution {
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { -1,1,0,0 };
//    int m, n;
//    vector<vector<int>> ret;
//    vector<vector<bool>> Pa;
//    vector<vector<bool>> At;
//
//public:
//    vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
//        m = h.size(), n = h[0].size();
//        Pa = At = vector<vector<bool>>(m, vector<bool>(n));
//        for (int j = 0; j < n; j++)
//        {
//            if (!Pa[0][j]) dfs(h, 0, j, Pa);
//            if (!At[m - 1][j]) dfs(h, m - 1, j, At);
//        }
//        for (int i = 0; i < m; i++)
//        {
//            if (!Pa[i][0]) dfs(h, i, 0, Pa);
//            if (!At[i][n - 1]) dfs(h, i, n - 1, At);
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (Pa[i][j] && At[i][j]) ret.push_back({ i,j });
//            }
//        }
//        return ret;
//    }
//    void dfs(vector<vector<int>>& h, int i, int j, vector<vector<bool>>& tmp)
//    {
//        tmp[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && !tmp[x][y] && h[i][j] <= h[x][y])
//            {
//                dfs(h, x, y, tmp);
//            }
//        }
//    }
//};
//class Solution {
//    int dx[8] = { 0,0,1,-1,-1,-1,1,1 };
//    int dy[8] = { 1,-1,0,0,-1,1,-1,1 };
//    int m, n;
//public:
//    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
//        int i = click[0], j = click[1];
//        m = board.size(), n = board[0].size();
//        if (board[i][j] == 'M')
//        {
//            board[i][j] = 'X';
//            return board;
//        }
//        dfs(board, i, j);
//        return board;
//    }
//    void dfs(vector<vector<char>>& board, int i, int j)
//    {
//        int cnt = 0;
//        for (int k = 0; k < 8; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
//                cnt++;
//        }
//        if (cnt)
//        {
//            board[i][j] = cnt + '0';
//            return;
//        }
//        else
//        {
//            board[i][j] = 'B';
//            for (int k = 0; k < 8; k++)
//            {
//                int x = i + dx[k], y = j + dy[k];
//                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
//                {
//                    dfs(board, x, y);
//                }
//            }
//        }
//    }
//};
//class Solution {
//    int m, n, cnt, ret;
//    int dx[2] = { 1,0 };
//    int dy[2] = { 0,1 };
//    bool vis[101][101];
//public:
//    int wardrobeFinishing(int _m, int _n, int _cnt) {
//        m = _m, n = _n, cnt = _cnt;
//        dfs(0, 0);
//        return ret;
//    }
//    void dfs(int i, int j)
//    {
//        vis[i][j] = true;
//        int tmpi = i, tmpj = j;
//        int sum = 0;
//        while (tmpi || tmpj)
//        {
//            sum = sum + tmpi % 10 + tmpj % 10;
//            tmpi /= 10;
//            tmpj /= 10;
//        }
//        if (sum > cnt) return;
//        else ret++;
//        for (int k = 0; k < 2; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x < m && y < n && !vis[x][y])
//                dfs(x, y);
//        }
//    }
//};